package algorithm
{
	import flash.utils.Dictionary;
	
	import struct.List;
	import struct.Node;
	import struct.OrderedList;

	public class AStarForMap
	{
		private var _passable:IPassable;
		private var _open:OrderedList;
		private var _step:int;
		private var _close:Dictionary;
		private var _nodeIndex:Dictionary;
		private var _edges:Array = [[1, 0], [-1, 0], [0, 1], [0, -1]];
		public var _toX:int;
		public var _toY:int;
		
		public var xMax:int;
		public var yMax:int;
		
		public var openNo:int = 0;
		
		public function AStarForMap(passable:IPassable, xMax:int, yMax:int)
		{
			_passable = passable;
			this.xMax = xMax;
			this.yMax = yMax;
		}
		
		public function solve(fromX:int, fromY:int, toX:int, toY:int):void {
			_toX = toX;
			_toY = toY;
			_open = new OrderedList;
			_close = new Dictionary();
			_nodeIndex = new Dictionary();
			openNo = 0;
			var node:AStarVertex = getNode(fromX, fromY);
			node.G = 0;
			node.H = 0;
			_open.add(node);
			var p:AStarVertex;
			while (_open.count > 0) {
				p = _open.unshift() as AStarVertex;
				for each (var offset:Array in _edges) {
					calculateDistance(p, p.x+offset[0], p.y+offset[1]);
				}
				addToS(p);				
				_open.print();
				if (p.x == toX && p.y == toY)
					break;
			}
		}
		
		public function getCloseSet():Dictionary {
			return _close;
		}
		
		public function getSearchSet():Dictionary {
			return _nodeIndex;
		}
		
		public function getNode(x:int, y:int):AStarVertex {
			var node:AStarVertex = findFromIndex(x, y);
			if (node == null) {
				node = new AStarVertex();
				node.x = x;
				node.y = y;
				node.G = int.MAX_VALUE;
				node.H = int.MAX_VALUE;
				node.searchNo = openNo++;
				addToIndex(node);
			}
			return node;
		}
		
		public function addToIndex(node:AStarVertex):void {
			_nodeIndex[key(node.x, node.y)] = node;
		}
		
		public function findFromIndex(x:int, y:int):AStarVertex {
			return _nodeIndex[key(x, y)];
		}
		
		public function key(x:int, y:int):Object {
			return x + y * xMax;
		}
		
		public function addToS(node:AStarVertex):void {
			_close[node] = node;			
		}
		
		public function isInClose(node:AStarVertex):Boolean {
			return _close[node] != null;
		}
		
		public function getH(node:AStarVertex, pre:AStarVertex):Number {
			var result:int = (Math.abs(node.x - _toX) + Math.abs(node.y - _toY)) * 2;
			if (pre.pre != null) {
				if ((pre.pre.x-pre.x) * (pre.y-node.y) != (pre.x-node.x) * (pre.pre.y-pre.y)) {
					result += 1;
				}
			}
			return result;
		}
		
		public function calculateDistance(pre:AStarVertex, x:int, y:int):void {
			if (!_passable.passable(x, y)) return;
			var node:AStarVertex = getNode(x, y);
			if (isInClose(node)) return;
			if (node.G + node.H > pre.G + 1 + getH(node, pre)) {
				node.G = pre.G +1;
				node.H = getH(node, pre);
				node.pre = pre;
				if (_open.hasContent(node)) {
					_open.updateToHead(node);
				} else {
					_open.add(node);
				}
			}
		}
	}
}